package 分类.二维动归;

public class 最小路径和 {

    public int minPathSum(int[][] grid) {
     int[][] memo=new int[grid.length][grid[0].length];
     memo[0][0]=grid[0][0];
     for (int i=1;i<memo.length;i++){
         memo[i][0]=memo[i-1][0]+grid[i][0];
     }
        for (int j=1;j<memo[0].length;j++){
            memo[0][j]=memo[0][j-1]+grid[0][j];
        }

        for (int i=1;i<memo.length;i++){
            for (int j=1;j<memo[0].length;j++){
                memo[i][j]=Math.min(memo[i-1][j],memo[i][j-1])+grid[i][j];
            }
        }
        return memo[memo.length-1][memo[0].length-1];
    }
}
